import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: lenovo
 * Date: 2023 -05 -01
 * Time: 11:36
 */

public class Work {
     class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(char val) {
            this.val = val;
        }

        TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public  TreeNode root=null;
public TreeNode creat(){
        TreeNode n1=new TreeNode('A');
    TreeNode n2=new TreeNode('B');
    TreeNode n3=new TreeNode('C');
    TreeNode n4=new TreeNode('D');
    TreeNode n5=new TreeNode('E');
    TreeNode n6=new TreeNode('F');
    TreeNode n7=new TreeNode('G');
    TreeNode n8=new TreeNode('H');
    n1.left=n2;
    n2.left=n4;
    n2.right=n5;
    n5.right=n8;
    n3.left=n6;
    n3.right=n7;
    n1.right=n3;
    root=n1;
    return root;
}

        public  List<Character> postorderTraversal(TreeNode root) {
            List<Character> list=new LinkedList<>();
           Stack<TreeNode> stack=new Stack<>();
           TreeNode cur=root;
           TreeNode top=null;
           if(cur==null){
               return list;
           }
           stack.push(cur);
           if(cur.left!=null){
               cur=cur.left;
           }else{
               cur=cur.right;
           }
           while(!stack.empty()){
               while(cur!=null){
                   stack.push(cur);
                   cur=cur.left;
               }
               //走到这里左边为null;
               while(cur==null&&!stack.empty()){
                   if(stack.peek().right==top){
                       top=stack.peek();
                       list.add(stack.pop().val);
                       //System.out.print(stack.pop().val+" ");
                   }else{
                       top=stack.peek();
                       cur=top.right;
                       if(cur==null){//右边为null
                           list.add(stack.pop().val);
                           //System.out.print(stack.pop().val+" ");
                       }else{
                           break;
                       }
                   }
               }
           }
           return list;
        }
    }

